#include <iostream>
#include <vector>
using namespace std;

int max_cost(vector<int> &val, int n, int op, int k, vector<vector<vector<int>>> &recd)
{
        if(k == 0){
                return 0;
        }

        if(n == val.size()){
                return 0;
        }

        if(recd[n][op][k] != -1){
                return recd[n][op][k];
        }

        int cost = 0;
        if(op == 1){
                cost = max_cost(val, n + 1, op, k, recd);
                cost = max(cost, max_cost(val, n + 1, 0, k, recd) - val[n]);
        }

        if(op == 0){
                cost = max_cost(val, n + 1, op, k, recd);
                cost = max(cost, max_cost(val, n + 1, 1, k - 1, recd) + val[n]);
        }
        return recd[n][op][k] = cost;
}

int main()
{
        int t = 0;
        cin >> t;
        while(t--){
                int n = 0;
                cin >> n;
                vector<int> value(n, 0);
                for(int i = 0; i < n; i++){
                        cin>>value[i];
                }
                vector<vector<vector<int>>> recd(n, vector<vector<int>>(2, vector<int>(3, -1)));
                cout<<max_cost(value, 0, 1, 2, recd)<<endl;
        }
        return 0;
}
/*
1
2
1 2
*/